/**
 * @file   IntervalTree.h
 * @author LiZhiqi
 * @date   Sat Dec 19 14:06:49 2020
 * 
 * @brief  A realization of interval tree
 *         based on binary search tree.
 * 
 */

#ifndef MGGS_IT
#define MGGS_IT

#define BLACK false
#define RED true

#include <iostream>
#include <cstdlib>
#include <algorithm>

template<typename T>
class IntervalTree
{
public:
    class Node
    {
    public:
      T low;
      T high;
      T max;
      Node* lc;
      Node* rc;
      Node* parent;
      bool color = RED; 
      Node(T _low, T _high);
    };
 protected:
    Node* root;
 public:
    IntervalTree() {root = NULL;};
    IntervalTree(T _low, T _high);
    ~IntervalTree();
    void update_max(Node* _x);
    void allupdate_max(Node* _x);
    Node* tree_search(T _low, T _high) const;
    Node* min(Node* _x) const;
    Node* max(Node* _x) const;
    Node* successor(Node* _x) const;
    Node* predecessor(Node* _x) const;
    void release(Node* _x);
    void insert(Node* _p);
    void insert(T _low, T _high);
    void transplant(Node *_u, Node *_v);
    void del(Node *_x);
    void del(T _low, T _high);
    void RightRotate(Node* _x);
    void LeftRotate(Node* _x);
    Node* Interval_Search(T _low, T _high);
    void test_Interval_Search(T _low, T _high);
};


template<typename T>
IntervalTree<T>::IntervalTree(T _low, T _high)
{
    Node* p = new Node(_low,_high);
    if (root == NULL)
	root = p;
};

template<typename T>
void IntervalTree<T>::release(Node* _x)
{
    if (_x != NULL)
    {
	release(_x->lc);
	release(_x->rc);
	delete _x;
    }	
};

template<typename T>
IntervalTree<T>::~IntervalTree()
{
    release(root);
};

template<typename T>
IntervalTree<T>::Node::Node(T _low, T _high)
{
    low = _low;
    high = _high;
    max = _high;
    parent = lc = rc = NULL;
};


template<typename T>
void IntervalTree<T>::update_max(Node* _x){
  if (_x->lc != NULL){
    if (_x->rc != NULL){
      if (_x->lc->max >= _x->rc->max && _x->lc->max > _x->max)
	_x->max = _x->lc->max;
      else if (_x->rc->max >= _x->lc->max && _x->rc->max > _x->max)
	_x->max = _x->rc->max;
    }
    else{
      if (_x->lc->max > _x->max)
	_x->max = _x->lc->max;
    }
  }
  else{
    if (_x->rc != NULL && _x->rc->max > _x->max)
      _x->max = _x->rc->max;
  }
}

template<typename T>
void IntervalTree<T>::allupdate_max(Node* _x){
  if (_x !=NULL){
    Node* y = _x;
    this->update_max(y);
    while (y->parent != NULL){
      y = y->parent;
      this->update_max(y);
    }
  }
}


template<typename T>
typename IntervalTree<T>::Node* IntervalTree<T>::successor(Node* _x) const
{
    Node* x = _x;
    if (x->rc != NULL)
	return min(x->rc);
    Node* y = x->parent;
    while (y != NULL && x == y->rc)
    {
	x = y;
	y = y->parent;
    }
    return y;
};

template<typename T>
typename IntervalTree<T>::Node* IntervalTree<T>::predecessor(Node* _x) const
{
  Node* x = _x;
  if (x->lc != NULL)
    return max(x->lc);
  Node* y = x->parent;
  while (y != NULL && x == y->lc){
    x = y;
    y = y->parent;
  }
  return y;
}

template<typename T>
typename IntervalTree<T>::Node* IntervalTree<T>::min(Node* _x) const
{
    while (_x->lc != NULL)
	_x = _x->lc;
    return _x;
};

template<typename T>
typename IntervalTree<T>::Node* IntervalTree<T>::max(Node* _x) const
{
  while (_x->rc != NULL)
    _x = _x->rc;
  return _x;
}


template<typename T>
void IntervalTree<T>::insert(Node* _p){
    Node* y = NULL;
    Node* x = root;
    while (x != NULL)
    {
	y = x;
	if (_p->low  < x->low)
	    x = x->lc;
	else
	    x = x->rc;
        if (_p->max > y->max)
	  y->max = _p->max;
    }
    _p->parent = y;
    if (y == NULL)
	root = _p;
    else if (_p->low < y->low)
	y->lc = _p;
    else
	y->rc = _p;
}


template<typename T>
void IntervalTree<T>::insert(T _low, T _high)
{
  Node* p = new Node(_low,_high);
    this->insert(p);
}


template<typename T>
typename IntervalTree<T>::Node* IntervalTree<T>::tree_search(T _low, T _high) const
{
  Node* x = root;
  while (x != NULL){
    if (x->low > _low)
      x = x->lc;
    else if (x->low < _low)
      x = x->rc;
    else{
      if (x->high == _high)
	return x;
      else
	x = x->rc;
    }   
  }
  return NULL;
}



template<typename T>
void IntervalTree<T>::transplant(Node *_u, Node *_v){
  if (_u == NULL){
    std::cerr << "Error! Can not transplant to a NULL."
                  << std::endl;
    std::exit(-1);
  }
  if (_u->parent == NULL)
    root = _v;  
  else if (_u == _u->parent->lc)
    _u->parent->lc = _v;
  else
    _u->parent->rc = _v;
  if (_v != NULL)
    _v->parent = _u->parent;
}

template<typename T>
void IntervalTree<T>::del(Node *_x){
  if (_x != NULL){
    if (_x->lc == NULL){
      this->transplant(_x, _x->rc);
      this->allupdate_max(_x->parent);
    }
    else if (_x->rc == NULL){
      this->transplant(_x, _x->lc);
      this->allupdate_max(_x->parent);
    }
    else{
      Node *y = min(_x->rc);
      Node *z = y->parent;
      if (y->parent != _x){
	this->transplant(y, y->rc);
	y->rc = _x->rc;
	y->rc->parent = y;
      }
      this->transplant(_x, y);
      y->lc = _x->lc;
      y->lc->parent = y;
      this->allupdate_max(z);
    }
    delete _x;
  }
}


template<typename T>
void IntervalTree<T>::del(T _low, T _high){
  Node* y = this->tree_search(_low,_high);
  this->del(y);  
}



template<typename T>
void IntervalTree<T>::RightRotate(Node* _x){
  Node* y = _x->lc;
  _x->lc = y->rc;
  if (y->rc != NULL)
    y->rc->parent = _x;
  y->parent = _x->parent;
  if (_x->parent == NULL)
    root = y;
  else if (_x == _x->parent->lc)
    _x->parent->lc = y;
  else
    _x->parent->rc = y;
  y->rc = _x;
  _x->parent = y;
  this->update_max(_x);
  this->update_max(y);
}


template<typename T>
void IntervalTree<T>::LeftRotate(Node* _x){
  Node* y = _x->rc;
  _x->rc = y->lc;
  if (y->lc != NULL)
    y->lc->parent = _x;
  y->parent = _x->parent;
  if (_x->parent == NULL)
    root = y;
  else if (_x == _x->parent->lc)
    _x->parent->lc = y;
  else
    _x->parent->rc = y;
  y->lc = _x;
  _x->parent = y;
  this->update_max(_x);
  this->update_max(y);
}

template<typename T>
typename IntervalTree<T>::Node* IntervalTree<T>::Interval_Search(T _low, T _high){
  Node* x = root;
  while(x != NULL && (_low > x->high || _high < x->low)){
    if (x->lc != NULL && _low <= x->lc->max)
      x = x->lc;
    else
      x = x->rc;
  }
  return x;
}

template<typename T>
void IntervalTree<T>::test_Interval_Search(T _low, T _high){
  Node* x = this->Interval_Search(_low,_high);
  if (x == NULL)
    std::cout << "No Interval!" << std::endl;
  else
    std::cout << "[" << x->low << "," << x->high << "]" << std::endl;
}



#else
// DO NOTHING.
#endif
